package java学习.leetcode.editor.cn;
/**
 * @author 刘世锦
 * 2022-10-30 17:13:35	 当前时间
 */
//给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 
//
// 
//
// 示例 1： 
//
// 
//输入：head = [1,2,3,4,5], n = 2
//输出：[1,2,3,5]
// 
//
// 示例 2： 
//
// 
//输入：head = [1], n = 1
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：head = [1,2], n = 1
//输出：[1]
// 
//
// 
//
// 提示： 
//
// 
// 链表中结点的数目为 sz 
// 1 <= sz <= 30 
// 0 <= Node.val <= 100 
// 1 <= n <= sz 
// 
//
// 
//
// 进阶：你能尝试使用一趟扫描实现吗？ 
// Related Topics 链表 双指针 
// 👍 2284 👎 0

public class 删除链表的倒数第N个结点{
	public static void main(String[] args) {
		Solution solution = new 删除链表的倒数第N个结点().new Solution();
		
	}
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
//输入：head = [1,2,3,4,5], n = 2
//输出：[1,2,3,5]

	/**
	 *   v     c
	 *  -1 1,2,3,4,5
	 *     1 2 3 4 5      2 1
	 *
	 */
    public ListNode removeNthFromEnd1(ListNode head, int n) {
		ListNode visual = new ListNode(-1);
		visual.next = head;
		ListNode cur = head;
		int len = 0;
		while (cur!=null){
			cur = cur.next; len++;
		}
		cur = visual;
		for (int i = 0; i < len-n; i++) {
			cur = cur.next;
		}
			cur.next = cur.next.next;
		return visual.next;
    }

    // 双指针。--快慢指针。
	/**  s
	 *     f
	 *  -1 1
	 *  -1 1,2,3,4,5
	 *
	 * 2
	 */
	public ListNode removeNthFromEnd(ListNode head, int n) {
		ListNode visual = new ListNode(-1);
		visual.next = head;
    	ListNode fast = visual,slow = visual;
    	while (fast.next!=null&&n>0){
    		fast = fast.next;
    		n--;
		}
    	while (fast.next!=null){
    		fast = fast.next;
    		slow  = slow.next;
		}
    	slow.next  = slow.next.next;
//    	若 [1],n=1,则返回[],此时返回head就不对了，应该返回 虚拟节点的下一个节点
    	return visual.next;
	}

	}
//leetcode submit region end(Prohibit modification and deletion)

}
